package com.二叉搜索树.练习题;

import java.util.LinkedList;

public class Leetcode938 {
    /**
     * 二叉搜索树的范围和
     * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
     * 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
     * 输出：32
     */
    public int rangeSumBST(TreeNode root, int low, int high) {
        TreeNode p = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while(p != null || !stack.isEmpty()){
            if (p != null){
                stack.add(p);
                p = p.left;
            }else {
                TreeNode pop = stack.pop();
                if(pop.val > high){
                    break;
                }
                if(pop.val >= low){
                    sum += pop.val;
                }
                p = pop.right;
            }
        }
        return sum;
    }
}
